package hot;

/**
 * @author way
 * @create 2025-03-14 22:21
 *  以上while循环中，若找到了target直接返回
 *
 *  当原数组不包含target时，考虑while循环最后一次执行的总是 left=right=mid,
 *
 *  此时nums[mid] 左边的数全部小于target，nums[mid]右边的数全部大于target,
 *
 *  则此时我们要返回的插入位置分为两种情况：
 *
 *  ①就是这个位置，即nums[mid]>target时，此时执行了right=mid-1，返回left正确 1 3  target 0
 *
 *  ②是该位置的右边一个，即nums[mid]<target时，此时执行了left=mid+1,返回left也正确 1 3  target 4
 *
 *
 */
public class _35_searchInsert {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int middle = 0;
        while (left <= right) {
            middle = left + (right - left) / 2;
            if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                return middle;
            }
        }
        return left;
    }
}
